package com.zhang.study.chapter02;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

import static com.zhang.util.RandomArrayUtil.randomArrayPlus;

/**
 * 一个数组中有一种数可能出现K次，其他数都出现了M次 M>1,K<M 找到，出现了K次的数,如果没有返回 -1
 * 要求，额外空间复杂度0(1)，时间复杂度0(N)
 */
public class Code04_KM_Plus {


    /**
     * 一个数组中有一种数可能出现K次，其他数都出现了M次 M>1,K<M 找到，出现了K次的数,如果没有返回 -1
     *
     * @param arr 数组
     * @param k   出现k的次数
     * @param m   出现的m的次数
     * @return 出现k次的数字
     */
    public static int onlyKTimes(int[] arr, int k, int m) {
        // 申请一个32位长度的数组
        int[] help = new int[32];
        // 遍历数组，统计每个数的二进制表示
        for (int num : arr) {
            for (int i = 0; i < 32; i++) {
                help[i] += (num >> i) & 1;
            }
        }
        int kNum = 0;
        for (int i = 0; i < 32; i++) {
            if ((help[i] % m) == 0) {
                continue;
            }
            if ((help[i] % m) == k) {
                kNum |= (1 << i);
            } else {
                return -1;
            }
        }
        if (kNum == 0) {
            int count = 0;
            for (int num : arr) {
                if (num == kNum) {
                    count++;
                }
            }
            if (count == k) {
                return kNum;
            } else {
                return -1;
            }
        }
        return kNum;

    }


    public static int test(int[] arr, int k, int m) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        int ans = -1;
        for (int num : map.keySet()) {
            if (map.get(num) == k) {
                ans = num;
                break;
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        int kindMax = 1000;
        int range = 1000;
        int times = 100000;
        int max = 9;
        for (int i = 0; i < times; i++) {
            int a = (int) (Math.random() * max) + 1; // a 1 ~ 9
            int b = (int) (Math.random() * max) + 1; // b 1 ~ 9
            int k = Math.min(a, b);
            int m = Math.max(a, b);
            if (k == m) {
                m++;
            }
            int[] randomArray = randomArrayPlus(kindMax, range, k, m);
            int ans1 = onlyKTimes(randomArray, k, m);
            int ans2 = test(randomArray, k, m);
            if (ans1 != ans2) {
                System.out.println("k =" + k + " m =" + m);
                System.out.println("ans1 = " + ans1 + " ans2 = " + ans2);
                Arrays.sort(randomArray);
                System.out.println(Arrays.toString(randomArray));
                return;
            }
        }
        System.out.println("Nice!");
    }


}
